#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Mapanqi
# 冒泡排序
# 稳定性: 稳定

# 稳定性: 假定在待排序的记录序列中, 存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中, ri=rj, 且ri在rj之前,而在排序后的序列中,ri仍在rj之前, 则称这种排序算法是稳定的,否则成为不稳定的.
# 结论: 假如列表有n个元素, 最坏情况下需要 N-1 轮排序 交换的次数
# -------------------------------------
# 最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）
# 最坏时间复杂度：O(n2)
# 稳定性：稳定
# -------------------------------------

#  [3,1,5,6,3,2,5,]

# 第一轮排序 （1+(n-1)）*（n-1）/2 =  n*(n-1)/2
# [1,3,5,6,3,2,5]
# [1,3,5,6,3,2,5]
# [1,3,5,6,3,2,5]
# [1,3,5,3,6,2,5]
# [1,3,5,3,2,6,5]
# [1,3,5,3,2,5,6]
# 第二轮排序
# [1,3,5,3,2,5,6]
# [1,3,5,3,2,5,6]
# [1,3,3,5,2,5,6]
# [1,3,3,2,5,5,6]
# [1,3,3,2,5,5,6]
# 第三轮排序
# [1,3,3,2,5,5,6]
# [1,3,3,2,5,5,6]
# [1,3,2,3,5,5,6]
# [1,3,2,3,5,5,6]
# 第四轮排序
# [1,3,2,3,5,5,6]
# [1,2,3,3,5,5,6]
# [1,2,3,3,5,5,6]
# 第五轮排序
# [1,2,3,3,5,5,6]
# [1,2,3,3,5,5,6]
# 第六轮排序
# [1,2,3,3,5,5,6]

a = [7, 6, 5, 4, 3, 2, 1]
# a = [1, 2, 3, 4, 5, 6, 7]
b = 0
c = 0
for i in range(len(a)-1, 0, -1):
    print("正在进行第{}轮排序".format(len(a)-i))
    for j in range(i):
        print("正在进行第{}第{}次排序".format(len(a)-i, j+1))
        if a[j] > a[j+1]:
            b += 1
            a[j], a[j+1] = a[j+1], a[j]
        c += 1
        print("第{}轮第{}次排序结果是{}".format(len(a)-1, j+1, a))
    print("第{}轮排序结果是{}".format(len(a)-i, a))

print(a)
print(b)
print(c)

